package com.peng.leetcode.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import com.google.common.base.Joiner;

/**
 * ThreeSum
 *
 * @author: lupeng6
 * @create: 2020/9/30 16:09
 */
public class ThreeSum {

    public static void main(String[] args) {
//        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
//        int[] nums = new int[]{1, 1, -2};
        int[] nums = new int[]{-1, 0, 1, 0};
//        System.out.println(Solution.threeSum(nums));
//        System.out.println(Solution1.threeSum(nums));
        System.out.println(Solution.threeSum(nums));
    }

    static class Solution {
        public static List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            List<Integer> aa = new ArrayList<Integer>();
            for (int num : nums) {
                aa.add(num);
            }
            Collections.sort(aa);
            for (int i = 0; i < aa.size(); i++) {
                if (i == 0 || aa.get(i) != aa.get(i - 1)) {
                    for (int second = i + 1; second < aa.size(); second++) {
                        if (second == i + 1 || aa.get(second) != aa.get(second - 1)) {
                            for (int t = second + 1; t < aa.size(); t++) {
                                if (t == second + 1 || aa.get(t) != aa.get(t - 1)) {
                                    int sum = aa.get(i) + aa.get(second) + aa.get(t);
                                    if (sum == 0) {
                                        List<Integer> temp = new ArrayList<Integer>();
                                        temp.add(aa.get(i));
                                        temp.add(aa.get(second));
                                        temp.add(aa.get(t));
                                        ret.add(temp);
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return ret;
        }
    }


    /**
     * 三层循环, 知道到三数和为0的
     * 要保证不能重复: 将找到的三个数排序,组成字符串,判断有没有找到过这个组合
     *
     * @author lupeng6
     * @date 2020/9/30 16:56
     */
//    static class Solution {
//        public static List<List<Integer>> threeSum(int[] nums) {
//            Set<String> set = new HashSet<String>();
//            List<List<Integer>> ret = new ArrayList<List<Integer>>();
//
//            for (int i = 0; i < nums.length; i++) {
//                for (int j = i + 1; j < nums.length; j++) {
//                    for (int k = j + 1; k < nums.length; k++) {
//                        if ((nums[i] + nums[j] + nums[k]) == 0) {
//                            List<Integer> integers = Arrays.asList(nums[i], nums[j], nums[k]);
//                            Collections.sort(integers);
//                            String join = Joiner.on("").join(integers);
//                            if (!set.contains(join)) {
//                                ret.add(integers);
//                                set.add(join);
//                            }
//                        }
//                    }
//                }
//            }
//            if (ret.size() > 0) {
//                return ret;
//            } else {
//                throw new RuntimeException("not find");
//            }
//        }
//    }


    /**
     * 利用 hash 表, 将所有的数都进去
     * 找两个数字相加, 然后取反, 去 hash 表中找.
     * 需要判断 取出来的值不是当前的两个值
     *
     * @author lupeng6
     * @date 2020/9/30 16:56
     */
    static class Solution1 {
        public static List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();

            Set<String> repeat = new HashSet<String>();

            Set<Integer> set = new HashSet<Integer>();
            for (int i = 0; i < nums.length; i++) {
                set.add(nums[i]);
            }

            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    int find = -(nums[i] + nums[j]);
                    if (set.contains(find) && find != nums[i] && find != nums[j]) {
                        List<Integer> integers = Arrays.asList(nums[i], nums[j], find);
                        Collections.sort(integers);
                        String join = Joiner.on("").join(integers);
                        if (!repeat.contains(join)) {
                            repeat.add(join);
                            ret.add(integers);
                        }
                    }
                }
            }

            return ret;
        }
    }

    /**
     * 先排序,
     *
     * @author lupeng6
     * @date 2020/9/30 16:56
     */
    static class Solution2 {
        public static List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();

            List<Integer> numList = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                numList.add(nums[i]);
            }
            Collections.sort(numList);

            Set<String> set = new HashSet<String>();

            for (int i = 1; i < numList.size(); i++) {
                if (numList.get(i) > 0) {
                    break;
                }
                int l = i - 1;
                int r = i + 1;
                while (l >= 0 && r < nums.length) {
                    int sum = numList.get(i) + numList.get(l) + numList.get(r);
                    if (sum == 0) {
                        if (!isRepeat(set, numList.get(i), numList.get(l), numList.get(r))) {
                            ret.add(Arrays.asList(numList.get(i), numList.get(l), numList.get(r)));
                        }
                        r++;
                    } else if (sum < 0) {
                        r++;
                    } else if (sum > 0) {
                        l--;
                    }
                }
            }

            return ret;
        }
    }


    private static boolean isRepeat(Set<String> set, int... ints) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < ints.length; i++) {
            list.add(ints[i]);
        }
        Collections.sort(list);
        String join = Joiner.on("").join(list);
        if (set.contains(join)) {
            return true;
        } else {
            set.add(join);
            return false;
        }
    }
}



